package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-07 00:17
 **/
public class LeetCode152 {

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        //记录以前一个位置为终点的最大值和最小值,后续位置为终点的最大值和最小值需要前一个推出
        for (int i = 1; i < n; ++i) {
            int mx = max;
            int mn = min;
            max = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            min = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            res = Math.max(res, max);
        }

        return res;
    }

    //暴力
    /*public int maxProduct(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            int multi = 1;
            for (int j = i; j < n; ++j) {
                multi *= nums[j];
                max = Math.max(multi, max);
            }
        }

        return max;
    }*/

}
